package _dp_base;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 279. 完全平方数
 */
public class No279 {
    ArrayList<Integer> list = new ArrayList<>();

    /**
     * 1. 递归方式
     */
    public int numSquares1(int n) {
        for (int i = 1; i * i <= n; i++) {
            list.add(i * i);
        }
        int length = list.size();
        return dfs(length - 1, n);
    }

    private int dfs(int i, int c) {
        if (i < 0) return c == 0 ? 0 : Integer.MAX_VALUE / 2;
        if (c < list.get(i)) return dfs(i - 1, c);
        else return Math.min(dfs(i - 1, c), dfs(i, c - list.get(i)) + 1);
    }

    /**
     * 2. 迭代方式
     */
    public int numSquares2(int n) {
        for (int i = 1; i * i <= n; i++) {
            list.add(i * i);
        }
        int length = list.size();

        int[][] f = new int[length + 1][n + 1];
        Arrays.fill(f[0], Integer.MAX_VALUE / 2);
        f[0][0] = 0;
        for (int i = 0; i < length; i++) {
            for (int c = 0; c < n + 1; c++) {
                if (c < list.get(i)) f[i + 1][c] = f[i][c];
                else f[i + 1][c] = Math.min(f[i][c], f[i + 1][c - list.get(i)] + 1);
            }
        }
        return f[length][n];
    }

    /**
     * 3. 滚动数组
     */
    public int numSquares3(int n) {
        for (int i = 1; i * i <= n; i++) {
            list.add(i * i);
        }
        int length = list.size();

        int[][] f = new int[2][n + 1];
        Arrays.fill(f[0], Integer.MAX_VALUE / 2);
        f[0][0] = 0;
        for (int i = 0; i < length; i++) {
            for (int c = 0; c < n + 1; c++) {
                if (c < list.get(i)) f[(i + 1) % 2][c] = f[i % 2][c];
                else f[(i + 1) % 2][c] = Math.min(f[i % 2][c], f[(i + 1) % 2][c - list.get(i)] + 1);
            }
        }
        return f[length % 2][n];
    }

    /**
     * 4. 一维数组
     */
    public int numSquares4(int n) {
        for (int i = 1; i * i <= n; i++) {
            list.add(i * i);
        }
        int length = list.size();

        int[] f = new int[n + 1];
        Arrays.fill(f, Integer.MAX_VALUE / 2);
        f[0] = 0;
        for (int i = 0; i < length; i++) {
            for (int c = list.get(i); c < n + 1; c++) {
                f[c] = Math.min(f[c], f[c - list.get(i)] + 1);
            }
        }
        return f[n];
    }

    /**
     * 4.1 进阶：去除集合
     */
    public int numSquares5(int n) {
        int[] f = new int[n + 1];
        Arrays.fill(f, Integer.MAX_VALUE / 2);
        f[0] = 0;
        for (int i = 1; i * i <= n; i++) {
            for (int c = i * i; c < n + 1; c++) {
                f[c] = Math.min(f[c], f[c - i * i] + 1);
            }
        }
        return f[n];
    }
}
